In computer science, a b-tree is a type of tree data structure. Unlike a binary tree where each node has exactly two children, a b-tree node may have a variable number of children. The number of children may vary within a range defined for the b-tree.
B-trees are used in applications including databases, file systems, and so on. Thus, a b-tree child node may store, for example, a key and a row identifier. In one example, the entries in a b-tree child node may be arranged in order by key value. In the example, each key in a non-child node (e.g., branch block) has an associated child node that is the root of a sub-tree containing nodes with keys less than or equal to the key but greater than the preceding key. A node may also have an additional right-most child that is the root for a sub-tree containing all keys greater than any keys in the node.
As data is inserted into a b-tree, a node may become full. Thus a node may be split to accommodate subsequent data insertions. Prior Art FIG. 1 illustrates an example of this splitting. At time T0, a b-tree may include a root node 100 that has a child node 110. Child node 110 may itself have two child nodes (e.g., a child node 120, a child node 130). At time T0 it may be determined that an insertion has caused the child node 130 to become full. Thus, at time T1, a median key 135 may be identified in the child node 130. At time T2, the median key 135 may be relocated to the node 110 and an additional child node 140 may be allocated and linked to the b-tree. A subset (e.g., half) of the keys that appeared in the child node 130 at time T1 will be located in the child node 130 at time T2. For example, keys with values less than that of the median key 135 may be located in the child node 130. Similarly, a subset (e.g., half) of the keys that appeared in the node 130 at time T1 will be located in the child node 140 at time T2. For example, keys with values greater than or equal to that of the median key 135 may be located in the child node 140 at time T2.
At certain times a b-tree may develop a “hot-spot”. A hot-spot describes a region (e.g., leaf node) that is experiencing a level of insertion activity that creates contention issues and/or other issues. For example, consider an online transaction processing system (OLTP) that handles transactions having sequentially increasing order numbers that are used as a key/index. When the OLTP experiences a certain level of activity, the rightmost block may become a hot-spot because an undesirable level of insertion activity may be focused in that rightmost block. Under these conditions, performing an operation like a split may lead to undesirable performance. While a rightmost block is identified, it is to be appreciated that other nodes may become hot-spots under other conditions.